/*
day145_2
2020.1.20
*/ 
#include<iostream>
#include<list>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;



class Solution {
public:
    string longestWord(vector<string>& words) 
	{
        unordered_map<string,int> m;
        for(int i=0;i<words.size();i++)	m[words[i]]=1;
        
        list<string> l;
        int max=0;
        for(int i=0;i<words.size();i++)
        {
        	string str=words[i];
        	int size=str.size();
        	string tem=str.substr(0,size-1);
        	if(m[tem]==1)
        	{
        		if(size==max) l.push_back(str);
        		if(size>max)
        		{
        			l.clear();
        			max=size;
        			l.push_back(str);
				}
			}
		}
		
		
		string res=l.front();
		for(auto &a :l)
		{
			res=res<a ? res : a;
		}
		
		return res;
    }
};


int main()
{
	vector<string> words={"a","banana","app","appl","ap","apply","apple"};
	Solution s;
	cout<<s.longestWord(words);
	return 0;
}
